Summary and Contributions: This paper presents a surrogate based end-to-end method to solve optimization problems where important decision parameters are unknown (and hence need to be inferred). In order to leverage the usual scalability and smoothness issues caused by usual "predict and optimize" approaches, the optimization problem is reparameterized by a learned surrogate that allows optimizing in a smaller dimensional space through a linear transformation. The authors provide some theoretical guarantees on the convexity and submodularity properties of the transformed optimization problem, on the partial pseudo-convexity of the re-parameterized learning problem and on the sample complexity of the predictive model learning task, thus arguing that such an approach should be in practice tractable and learnable with gradient descent (in spite of the non-convexity of the reparameterized learning problem). They also provide experiments carried out in three types of configurations, including convex, non-convex and submodular optimization problems and compare both the performance and scalability of the approach to (1) a two-stage approach that uses a separate ground truth-based model prior to optimization on the inferred parameters and (2) a classical end-to-end decision-focused method. The presented approach seems to significantly improve the performances when solving problems with numerous possible local optima (i.e.

Solving optimization problems with unknown parameters often requires learning a predictive model to predict the values of the unknown parameters and then solving the problem using these values. Recent work has shown that including the optimization problem as a layer in the model training pipeline results in predictions of the unobserved parameters that lead to higher decision quality. Unfortunately, this process comes at a large computational cost because the optimization problem must be solved and differentiated through in each training iteration; furthermore, it may also sometimes fail to improve solution quality due to non-smoothness issues that arise when training through a complex optimization layer. To address these shortcomings, we learn a low-dimensional surrogate model of a large optimization problem by representing the feasible space in terms of meta-variables, each of which is a linear combination of the original variables. By training a low-dimensional surrogate model end-to-end, and jointly with the predictive model, we achieve: i) a large reduction in training and inference time; and ii) improved performance by focusing attention on the more important variables in the optimization and learning in a smoother space.